#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;
//要定义从小到大的优先队列
priority_queue<long long,vector<long long>,greater<long long>> pq;
set<long long> s;
int main(void){
    pq.push(1);
    s.insert(1);
    for(int i=1;;i++){
        long long res=pq.top();
        //注意要pop 否则每次都同一个出来
        pq.pop();
        if(i==1500){
            printf("The 1500'th ugly number is %lld.\n",res);
        }
        else{
            long long xt=2*res;
            if(!s.count(xt)){
                s.insert(xt);
                pq.push(xt);
            }
            xt=3*res;
            if(!s.count(xt)){
                s.insert(xt);
                pq.push(xt);
            }
            xt=5*res;
            if(!s.count(xt)){
                s.insert(xt);
                pq.push(xt);
            }
        }
    }
    return 0;
}
